﻿//https://leetcode.cn/problems/longest-increasing-subsequence/

class Solution {
    int memo[2501];
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            ret = max(ret, dfs(i, nums));
        }

        return ret;

    }

    int dfs(int pos, vector<int>& nums)
    {
        //检查是否已被计算过
        if (memo[pos])
        {
            return memo[pos];
        }

        int ret = 1;
        for (int i = pos + 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[pos])
            {
                ret = max(ret, dfs(i, nums) + 1);
            }
        }
        memo[pos] = ret;

        return ret;
    }
};